package cn.edu.jxau.test;

import java.util.Arrays;

import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Stack;

/**
 * DFS拓扑排序算法:寻找出度为0的顶点
 * 时间复杂度是O(V+E)
 * 
 * @author 付大石
 */
public class DFSTopological {

    public static void main(String[] args) {

        // 有向无环图 //
//        DirectedGraph g = new DirectedGraph(13);
//        g.addEdge(0, 1);
//        g.addEdge(0, 5);
//        g.addEdge(0, 6);
//        g.addEdge(2, 0);
//        g.addEdge(2, 3);
//        g.addEdge(3, 5);
//        g.addEdge(5, 4);
//        g.addEdge(6, 9);
//        g.addEdge(6, 4);
//        g.addEdge(7, 6);
//        g.addEdge(8, 7);
//        g.addEdge(9, 11);
//        g.addEdge(9, 10);
//        g.addEdge(9, 12);
//        g.addEdge(11, 12);
//        for (int i : new DFSTopological(g).order()) {
//            System.out.print(i + " ");
//        }

        // 有向有环图 //
        DirectedGraph g = new DirectedGraph(6);
        g.addEdge(0, 5);
        g.addEdge(5, 4);
        g.addEdge(4, 3);
        g.addEdge(3, 5);
        for (int i : new DFSTopological(g).cycle()) {
            System.out.print(i + " ");
        }
    }

    /**
     * topo排序序列
     */
    private Stack<Integer> order;

    /**
     * 标记数组
     */
    private boolean[] marked;

    /**
     * 由于检测是由有环
     */
    private boolean[] onStack;

    /**
     * 如果有环的话，用于构造环的信息
     */
    private int[] edgeTo;

    /**
     * 环
     */
    private Stack<Integer> cycle;

    public DFSTopological(DirectedGraph g) {

        order = new LinkedStack<>();
        marked = new boolean[g.v()];
        edgeTo = new int[g.v()];
        onStack = new boolean[g.v()];
        for (int i = 0, end = g.v(); i < end; i++) {
            if (!marked[i])
                dfs(g, i);
        }
    }

    /**
     * 深度优先遍历
     * 
     * @param g
     * @param i
     */
    private void dfs(DirectedGraph g, int v) {

        marked[v] = true;
        onStack[v] = true;
        for (int w : g.adj(v)) {
            if (cycle != null) { // 有环
                return;
            } else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(g, w);
            } else if (onStack[w]) { // 检测到有环，尝试构造环
                cycle = new LinkedStack<>();
                System.out.println(Arrays.toString(edgeTo));
                for (int i = v; i != w; i = edgeTo[i]) {
                    cycle.push(i);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
        order.push(v);
    }

    public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable<Integer> cycle() {
        return cycle;
    }

    public Iterable<Integer> order() {
        if (hasCycle()) {
            throw new RuntimeException("有向有环图无法进行topological排序");
        }
        return order;
    }
}
